package com.kevin.Code.OfferReviewVersion2;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Vinlee Xiao
 * @Classname AllPathsFromSourceToTarget
 * @Description Leetcode 797. 所有可能的路径 同剑指Offer 110 中等难度
 * @Date 2022/1/14 21:03
 * @Version 1.0
 */
public class AllPathsFromSourceToTarget {

    /**
     * 深度优先遍历
     *
     * @param graph
     * @return
     */
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {

        List<List<Integer>> result = new LinkedList<>();
        List<Integer> combine = new LinkedList<>();
        dfs(graph, result, combine, 0);
        return result;
    }

    /**
     * 为有向图不用担心 重复访问
     *
     * @param graph
     * @param result
     * @param combine
     * @param vertex
     */
    private void dfs(int[][] graph, List<List<Integer>> result, List<Integer> combine, int vertex) {
        //递归结束条件
        if (vertex == graph.length - 1) {
            combine.add(vertex);
            result.add(new LinkedList<>(combine));
            return;
        }
        combine.add(vertex);
        //顶点v的邻接点
        int[] neighbor = graph[vertex];
        for (int v : neighbor) {
            dfs(graph, result, combine, v);
        }
        combine.remove(combine.size() - 1);
    }
}
